/**
 * @version Create on 2012-11-1
 * @author Yinzi Chen
 */

public class FirstMissingPositive {

	public int firstMissingPositive(int[] A) {
		int n = A.length;
		for (int i = 0; i < n; ++i) {
			while (A[i] != i + 1 && A[i] > 0 && A[i] <= n
					&& A[i] != A[A[i] - 1]) {
				int tmp = A[i];
				A[i] = A[A[i] - 1];
				A[tmp - 1] = tmp;
			}
		}
		for (int i = 0; i < n; ++i)
			if (A[i] != i + 1)
				return i + 1;
		return n + 1;
	}

	public static void main(String[] args) {
		FirstMissingPositive a = new FirstMissingPositive();
		a.firstMissingPositive(new int[] { 2, 1 });
	}

}
